/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Owner
 */
public class RedBlack implements WordSet {

    /**
     *
     * @param wordObject
     */
    @Override
    public void add(Word wordObject) {
        root = root.add(wordObject);
        root.color = Color.BLACK;
    }

    /**
     *
     * @param word
     * @return (null if not found)
     */
    @Override
    public Word get(Word word) {
        Node n = root.getNode(word);
        if (n != null) {
            return n.word;
        } else {
            return null;
        }
    }

    private enum Color {RED, BLACK};


    private static final int LESS    = -1;

    private static final int EQUAL   =  0;

    private static final int GREATER = +1;

    private Node root;

    final private Node EMPTY = new Empty();

    public RedBlack() {
        root = EMPTY;
    }
    
    public boolean contains(Word word) {
        return root.getNode(word) != null;
    }

    private class Node {
        public Word    word;
        
        public Color  color;
        public Node   left;
        public Node   right;

        protected Node() {
            assert EMPTY == null;
        }

        public Node(Word k) {
            word   = k;
            color = Color.RED;
            left  = EMPTY;
            right = EMPTY;
        }
        
        private boolean isRed() {
            return color == Color.RED;
        }

        public Node add(Word k) {
            switch (k.compareTo(word)) {
            case LESS:
                left = left.add(k);
                break;

            case GREATER:
                right = right.add(k);
                break;

            case EQUAL:

                word = k;
                return this;  
            }
        
            if (left.isRed() && left.left.isRed()) {

                return balance(left.left, left, this,              
                               left.left.right, left.right);       

            } else if (left.isRed() && left.right.isRed()) {

                return balance(left, left.right, this,             
                               left.right.left, left.right.right); 
                
            } else if (right.isRed() && right.left.isRed()) {

                return balance(this, right.left, right,            
                               right.left.left, right.left.right); 
                
            } else if (right.isRed() && right.right.isRed()) {

                return balance(this, right, right.right,           
                               right.left, right.right.left);      
            }

            return this;
        }

        public Node getNode(Word k) {
            switch (k.compareTo(word)) {
            case LESS:
                return left.getNode(k);

            case GREATER:
                return right.getNode(k);

            default: // EQUAL
                return this;
            }
        }

    }


    private class Empty extends Node {

        public Empty() {
            color = Color.BLACK;
            assert EMPTY == null : "Should only make one empty node instance!";
        }


        public Node add(Word k) {
            return new Node(k);
        }

        public Node getNode(Word word) {
            return null;
        }
    }

    private Node balance(Node x, Node y, Node z, Node B, Node C) {
        
        x.right = B;
        y.left  = x;
        y.right = z;
        z.left  = C;
        x.color = Color.BLACK;
        y.color = Color.RED;
        z.color = Color.BLACK;
        return y;
    }
}

